Groupe D - Tri par fusion

Principe : le tri par fusion divise le jeu de cartes en deux moitiés, trie chacune des moitiés de manière récursive, puis fusionne les deux moitiés triées en une seule partie ordonnée. Ce processus de division et de fusion assure que le jeu entier est trié.

Exemple : imaginons un petit jeu de cartes avec les valeurs [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5].

1. Division : diviser le jeu de cartes en deux parties jusqu'à ce que chaque sous-partie contienne une ou deux cartes. Par exemple, diviser [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] en deux parties [3, 1, 4, 1, 5] et [9, 2, 6, 5, 3, 5].
   
2. Tri récursif : continuer à diviser chaque partie jusqu'à ce qu'on ne puisse plus diviser (chaque partie devient une seule carte ou deux cartes). Ensuite, trier chaque petite partie. Par exemple, [3, 1] devient [1, 3] après tri.
   
3. Fusion : fusionner les parties triées ensemble. Lors de la fusion, prendre les cartes une par une de chaque partie, en choisissant à chaque fois la plus petite carte disponible pour la mettre dans le jeu final. Par exemple, fusionner [1, 3] et [1, 4, 5] donnerait [1, 1, 3, 4, 5].